package com.jack.newTech;

import com.google.common.hash.Funnels;
import com.google.common.hash.Hashing;
import com.google.common.math.LongMath;
import com.google.common.primitives.Ints;
import com.google.common.primitives.Longs;
import com.sun.istack.internal.Nullable;

import java.math.RoundingMode;
import java.nio.charset.Charset;
import java.util.Arrays;

import static com.google.common.base.Preconditions.checkArgument;

/**
 * 仿造Guava BloomFilter实现的只支持String类型的BitMap
 * 位图算法
 * Created by zhang_j on 2020/7/14
 */
public class BitMap {

    //预估元素数量
    private int numberAppros;
    //可接受的误差率
    private double fpp;
    //自动计算的最有哈希函数个数
    private int numHashFunctions;
    //自动计算的最有BitMap长度
    private int bitmapLength;
    //二进制向量组
    private final BitArray bits;

    public BitMap(int numbers, double fpp){
        this.numberAppros = numbers;
        this.fpp = fpp;

        bitmapLength = (int) (-numbers * Math.log(fpp) / (Math.log(2) * Math.log(2)));
        numHashFunctions = Math.max(1, (int) Math.round((double) bitmapLength / numbers * Math.log(2)));
        bits = new BitArray(bitmapLength);
    }

    public boolean mightContain(String element){
        long bitSize = bits.bitSize();
        /**
         * 一致性hash算法，生成128位key
         */
        byte[] bytes = Hashing.murmur3_128().hashObject(element, Funnels.stringFunnel(Charset.forName("UTF-8"))).asBytes();

        long hash1 = Longs.fromBytes(
                bytes[7], bytes[6], bytes[5], bytes[4], bytes[3], bytes[2], bytes[1], bytes[0]
        );
        long hash2 = Longs.fromBytes(
                bytes[15], bytes[14], bytes[13], bytes[12], bytes[11], bytes[10], bytes[9], bytes[8]
        );

        long combinedHash = hash1;
        for (int i = 0; i < numHashFunctions; i++) {
            if(!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)){
                return false;
            }
            combinedHash += hash2;
        }
        return true;
    }

    public boolean insert(String element){
        long bitSize = bits.bitSize();
        /**
         * 一致性hash算法，生成128位key
         */
        byte[] bytes = Hashing.murmur3_128().hashObject(element, Funnels.stringFunnel(Charset.forName("UTF-8"))).asBytes();

        long hash1 = Longs.fromBytes(
                bytes[7], bytes[6], bytes[5], bytes[4], bytes[3], bytes[2], bytes[1], bytes[0]
        );
        long hash2 = Longs.fromBytes(
                bytes[15], bytes[14], bytes[13], bytes[12], bytes[11], bytes[10], bytes[9], bytes[8]
        );

        boolean bitsChanged = false;
        long combinedHash = hash1;
        for (int i = 0; i < numHashFunctions; i++) {
            // Make the combined hash positive and indexable
            bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);
            combinedHash += hash2;
        }
        return bitsChanged;
    }

    static final class BitArray {
        final long[] data;
        long bitCount;

        BitArray(long bits) {
            this(new long[Ints.checkedCast(LongMath.divide(bits, 64, RoundingMode.CEILING))]);
        }

        // Used by serialization
        BitArray(long[] data) {
            checkArgument(data.length > 0, "data length is zero!");
            this.data = data;
            long bitCount = 0;
            for (long value : data) {
                bitCount += Long.bitCount(value);
            }
            this.bitCount = bitCount;
        }

        boolean set(long index) {
            if (!get(index)) {
                data[(int) (index >>> 6)] |= (1L << index);
                bitCount++;
                return true;
            }
            return false;
        }

        boolean get(long index) {
            return (data[(int) (index >>> 6)] & (1L << index)) != 0;
        }

        long bitSize() {
            return (long) data.length * Long.SIZE;
        }

        long bitCount() {
            return bitCount;
        }

        void putAll(BitArray array) {
            checkArgument(
                    data.length == array.data.length,
                    "BitArrays must be of equal length (%s != %s)",
                    data.length,
                    array.data.length);
            bitCount = 0;
            for (int i = 0; i < data.length; i++) {
                data[i] |= array.data[i];
                bitCount += Long.bitCount(data[i]);
            }
        }

        @Override
        public boolean equals(@Nullable Object o) {
            if (o instanceof BitArray) {
                BitArray bitArray = (BitArray) o;
                return Arrays.equals(data, bitArray.data);
            }
            return false;
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(data);
        }
    }

}
